package com.linyaonan.leetcode.easy._744;

/**
 * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
 *
 * 在比较时，字母是依序循环出现的。举个例子：
 *
 * 如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'
 *  
 *
 * 示例 1：
 *
 * 输入: letters = ["c", "f", "j"]，target = "a"
 * 输出: "c"
 * 示例 2:
 *
 * 输入: letters = ["c","f","j"], target = "c"
 * 输出: "f"
 * 示例 3:
 *
 * 输入: letters = ["c","f","j"], target = "d"
 * 输出: "f"
 *  
 *
 * 提示：
 *
 * 2 <= letters.length <= 104
 * letters[i] 是一个小写字母
 * letters 按非递减顺序排序
 * letters 最少包含两个不同的字母
 * target 是一个小写字母
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-smallest-letter-greater-than-target
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 看到letters是升序排序的，很自然想到二分法，由于是循环的数值，那么先考虑边界，如果大于最大值，那么直接返回index=0；同理小于最小值，直接返回index=length - 1
     *
     * 排查边界之后，那么目标值一定在数组中，目标就转换为求最左侧匹配大于等于目标值
     * @param letters
     * @param target
     * @return
     */
    public char nextGreatestLetter(char[] letters, char target) {
        int t = target - 'a';
        int lenght = letters.length;
        if (letters[lenght - 1] - 'a' < t) {
            return letters[0];
        }
        int l = 0;
        int r = lenght - 1;
        char p = letters[0];
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int midT = letters[mid] - 'a';
            if (t < midT) {
                r = mid - 1;
                p = letters[mid];
            } else {
                l = mid + 1;
            }
        }
        return p;
    }
}